import java.util.*;

public class Sort {
	
	private int[] lista;
	private int[] ordena;
	
	public Sort(int num)
	{
		this.lista=new int[num];
		Random rand=new Random();
		
		for (int i=0;i<num;i++)
			lista[i]=rand.nextInt();
				
		
	}
	
	public int[] getLista()
	{
		return lista;
	}
	
	public int[] getOrdenada()
	{
		return ordena;
	}
	
	public void selectionSort()
	{
		
		for(int i=0;i<lista.length - 1;i++)
		{
			int min=i;
			for(int j=i+1;j<lista.length;j++)
			{
				if(lista[j]<lista[min])
					min=j;
			}
			if(i!=min)
			{
				int aux=lista[i];
				lista[i]=lista[min];
				lista[min]=aux;
			}
			
		}

		ordena=lista;
		
	}
	
	public void  otraSelectionSort()
	{
		
		for(int i=0;i<ordena.length - 1;i++)
		{
			int min=i;
			for(int j=i+1;j<ordena.length;j++)
			{
				if(ordena[j]<ordena[min])
					min=j;
			}
			if(i!=min)
			{
				int aux=ordena[i];
				ordena[i]=ordena[min];
				ordena[min]=aux;
			}
			
		}
		
	}
	
	
     public int[] OrdenaMerge(int[] L) {
        int n = L.length;
 
        if (n > 1){
            int m = (int) (Math.ceil(n/2.0));
            int [] L1 = new int[m];
            int [] L2 = new int[n-m];
 
            for (int i = 0; i < m; i++){
                L1[i] = L[i];
            }
            for (int i = m; i < n; i++){
                L2[i-m] = L[i];
            }
            L = merge(OrdenaMerge(L1), OrdenaMerge(L2));
        }
        return L;
    }
 
    public int[] eliminar(int [] l){
        int [] L = new int[l.length-1];
        for(int i = 1; i < l.length; i++){
            L[i-1] = l[i];
        }
        return L;
    }
 
    public int[] merge(int[] L1, int[] L2) {
         int[] L = new int[L1.length+L2.length];
         int i = 0;
         while ((L1.length != 0) && (L2.length != 0)) {
             if (L1[0] < L2[0]){
                 L[i++] = L1[0];
                 L1 = eliminar(L1);
                 if (L1.length == 0){
                     while (L2.length != 0) {
                         L[i++] = L2[0];
                         L2 = eliminar(L2);
                     }
                 }
             }
             else{
                 L[i++] = L2[0];
                 L2 = eliminar(L2);
                 if (L2.length == 0) {
                    while (L1.length != 0) {
                         L[i++] = L1[0];
                         L1 = eliminar(L1);
                    }
                 }
             }
         }
         return L;
    }
}